package com.zyk.grate_offer.class07;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/5/15 15:46
 */
public class Code03_MaxGap {

    public static int maxGap(int[] nums) {
        if (nums == null || nums.length < 2)
            return 0;
        int N = nums.length, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        if (max == min) return 0;
        // 当前桶是否有数字, 当前桶的最大值, 当前桶的最小值
        boolean[] hasNum = new boolean[N + 1];
        int[] maxs = new int[N + 1];
        int[] mins = new int[N + 1];
        int bid;    // 桶号
        for (int i = 0; i < N; i++) {
            bid = bucket(nums[i], max, min, N);
            maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
            mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
            hasNum[bid] = true;
        }
        int res = 0;
        int lastMax = maxs[0];
        int i = 1;
        for (; i <= N; i++) {
            if (hasNum[i]) {
                res = Math.max(res, mins[i] - lastMax);
                lastMax = maxs[i];
            }
        }
        return res;
    }

    // 最大值max, 最小值min, len+1个桶
    // 返回num应该被分到哪儿个桶里边
    public static int bucket(long num, long max, long min, long len) {
        return (int) ((num - min) * len / (max - min));
    }

    // for test
    public static int comparator(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        Arrays.sort(nums);
        int gap = Integer.MIN_VALUE;
        for (int i = 1; i < nums.length; i++) {
            gap = Math.max(nums[i] - nums[i - 1], gap);
        }
        return gap;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static void main(String[] args) {
//        int[] arr = {62, 9, 87, 2, 19, 0, 0, 87, 31};
//        System.out.println(maxGap(arr));

        int testTime = 500000;
        int maxSize = 9;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            int ans1 = maxGap(arr1);
            int ans2 = comparator(arr2);
            if (ans1 != ans2) {
                System.out.println(Arrays.toString(arr1));
                System.out.println(ans1 + "\t" + ans2);
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }


}
